<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <!-- 5.最长回文子串
        给你一个字符串 s，找到 s 中最长的回文子串。

        如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

        示例 1：

        输入：s = "babad"
        输出："bab"
        解释："aba" 同样是符合题意的答案。
        
        示例 2：

        输入：s = "cbbd"
        输出："bb"
     -->
    <script>
        // 思路：定义dp[i][j]表示子串i～j是否是回文子串，循环s的子串，看是否满足s[i]，s[j]相等，如果相等，则dp[i][j]是否为回文串取决于dp[i+1][j-1]是否也是回文子串，在循环的过程中不断更新最大回文子串的长度，注意子串的长度是0或1也算回文子串
        // 复杂度：时间复杂度O(n^2)，两层循环。空间复杂度O(n^2)，即动态规划dp数组的空间。
        var longestPalindrome = function (s) {
            let n = s.length;
            let res = '';
            let dp = Array.from(new Array(n), () => new Array(n).fill(false))//初始化数组 
            for (let i = n - 1; i >= 0; i--) {//循环字符串
                for (let j = i; j < n; j++) {
                    //dp[i][j]表示子串i～j是否是回文子串
                    //回文子串必须满足s[i]，s[j]相等。并且向外扩展一个字符也相等，即dp[i+1][j-1]也是回文子串
                    //j - i < 2表示子串小于等于1也是回文串
                    dp[i][j] = s[i] == s[j] && (j - i < 2 || dp[i + 1][j - 1])
                    if (dp[i][j] && j - i + 1 > res.length) {//当前回文子串比之前的大，更新最大长度
                        res = s.substring(i, j + 1)
                    }
                }
            }
            console.log(res)
        };
        longestPalindrome('ababd')
    </script>
</body>

</html>